class Solution {
    public int[] sortArray(int[] nums) {
        //用三指针的算法
        int left = 0;
        int right = nums.length - 1;
        quickSort(nums, left, right);
        return nums;
    }
    private void quickSort(int[] nums, int l, int r){
        if(l >= r) return;
        //int tmp = nums[new Random().nextInt(r - l + 1) + l];
        int tmp = nums[l];
        int left = l - 1;
        int right = r + 1;
        int cur = l;
        while(cur < right){
            if(nums[cur] < tmp){
                swap(nums, ++left, cur++);
            }else if(nums[cur] == tmp){
                cur++;
            }else{
                swap(nums, --right, cur);
            }
        }
        //[l, left] [left + 1, right - 1] [right, r]
        quickSort(nums, l, left);
        quickSort(nums, right, r);
    }
    private void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
